package test;

import comment.Comment;

/**
 *create by tbj
 */
public class MyQuick_three {
	private static void _sort(int[] a,int l,int r){
		if(l >= r){
			return ;
		}
		Comment.swapIntArr(a, l, (int)Math.random()*(r-l+1)+l);
		int v=a[l];
		int lt=l;
		int gt=r+1;
		int i=l+1;
		while(i < gt){
			if(a[i]<v){
				Comment.swapIntArr(a, i, lt+1);
				lt++;
				i++;
			}else if(a[i]>v){
				Comment.swapIntArr(a, i, gt-1);
				gt--;
			}else{
				i++;
			}
		}
		Comment.swapIntArr(a, l, lt);
		_sort(a, l, lt-1);
		_sort(a, gt, r);
	}
	public static void sort(int[] a){
		_sort(a,0,a.length-1);
	}
	public static void main(String[] args) {
		int[] a=Comment.getSortIntArr();
		MyQuick_three.sort(a);
		for (int i : a) {
			System.out.print(i+" ");
		}
	}
}
